package leecode.array.二分查找问题;

/**
 * @author wangxi created on 2021/5/23 20:49
 * @version v1.0
 *
 * 从0,1,2,...,n这n+1个数中选择n个数，找出这n个数中缺失的那个数，要求O(n)尽可能小.
 *
 * 题目如果数组有序，那么使用二分即为 logn
 *
 * leetcode非有序： https://leetcode-cn.com/problems/missing-number/
 */
public class FindMissingNumberV2 {



    public int solve (int[] a) {
        // write code here
        if (a == null || a.length <= 0) {
            return 0;
        }
        // 如果是有序的，二分查找
        int left = 0;
        int right = a.length -1;
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (a[mid] == mid) {
                left = mid + 1;
            } else if (a[mid] > mid) {
                right = mid - 1;
            }
        }
        return left;
    }
}
